package 蓝桥._2024.最大异或结点;

public class _01_trieTree {
    // 01字典树
    static class Trie {
        Trie[] next = new Trie[2];

        static void insert(Trie trie, int n){
            for(int i=0;i<32;i++){
                // 先插入尾部
                int m = n % 2;
                n = n >> 1;
                if(trie.next[m]==null){
                    trie.next[m] = new Trie();
                    trie = trie.next[m];
                }else{
                    trie = trie.next[m];
                }
            }
        }

        static boolean find(Trie trie, int n){
            for(int i=0;i<32;i++){
                // 先尾部
                int m = n % 2;
                n = n >> 1;
                if(trie.next[m]==null)
                    return false;
                trie = trie.next[m];
            }
            return true;
        }

        static void remove(Trie trie, int n){
            for(int i=0;i<31;i++){
                // 先尾部
                int m = n % 2;
                n = n >> 1;
                trie = trie.next[m];
            }
            int m = n % 2;
            trie.next[m] = null;
        }

        public static void main(String[] args) {
            Trie trie = new Trie();

            boolean a = find(trie, 1);
            System.out.println(a);

            Trie.insert(trie,1);
            boolean b = find(trie, 1);
            System.out.println(b);
            Trie.remove(trie,1);

            boolean c = find(trie, 1);
            System.out.println(c);

            System.out.println(2&1);
            System.out.println(1&1);
            System.out.println(4&1);

        }
    }
}
